/*
 * @lc app=leetcode.cn id=1585 lang=cpp
 *
 * [1585] 检查字符串是否可以通过排序子字符串得到另一个字符串
 */

// @lc code=start
class Solution
{
public:
    bool isTransformable(string s, string t)
    {
        vector<queue<int>> pos(10);
        for (int i = 0; s[i]; i++)
        {
            pos[s[i] - '0'].push(i);
        }

        for (int i = 0; t[i]; i++)
        {
            int num = t[i] - '0';
            if (pos[num].empty())
            {
                return false;
            }
            int p = pos[num].front();
            for (int j = 0; j < num; j++)
            {
                if (!pos[j].empty() && pos[j].front() < p)
                {
                    return false;
                }
            }
            pos[num].pop();
        }

        return true;
    }
};
// @lc code=end
